We just established that Linked Lists utilize dynamic pointers for efficient $O(1)$ updates when the number of elements, $n$, is volatile. Now, we must understand the structure they are most often contrasted against: the Array.

  • An array is defined by its use of contiguous memory. All elements are stored adjacent to one another in a single block of memory.
  • This structure enables random access, meaning any element can be reached directly without traversing previous elements.
  • The memory address of an element at index $i$ is calculated using the formula: $BaseAddress + i \times ElementSize$.
  • This calculation ensures that reading or accessing any item is an incredibly efficient operation, always completing in $O(1)$ time complexity.
  • However, insertion or deletion in the middle requires shifting $O(n)$ elements to maintain contiguity, making these operations slow.

Key Property: Random Access

An array is a sequential collection where the physical order in memory directly corresponds to the logical order of the elements. The use of indices allows us to calculate the exact memory location of any item instantly, guaranteeing $O(1)$ access time.